package main.old.old_2022;

import java.util.*;

/**
 * @Author: Take-off
 * 876.链表的中间结点：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
 *
 * 142. 环形链表 II：给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 不允许修改 链表。
 *
 *
 * @Description: TODO
 * @Date: 2022/7/21 6:49 AM
 * @Version: 1.0
 **/
public class Solution0721 {

    //876.链表的中间结点- 链表问题暴力方法市遍历放到数组中
    public ListNode middleNode(ListNode head) {
        ListNode[] listNodes = new ListNode[100];
        int t = 0;
        while (head != null){
            listNodes[t] = head;
            head = head.next;
            t++;
        }
        ListNode listNode = new ListNode();
        if (t % 2 == 1){
            // 单数
             listNode = listNodes[(t -1)  / 2];
        }else {
             listNode = listNodes[t  / 2];
        }
        return listNode;
    }

    //142. 环形链表 II- 遇到是否重复的问题可以用哈希表来解决
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> listNodes = new HashSet<>();
        ListNode pos = head;
        while (pos != null){
            if (!listNodes.contains(pos)){
                listNodes.add(pos);
            }else {
                return pos;
            }
            pos = pos.next;
        }
        return null;
    }

    //142. 环形链表 II-快慢指针，一个指针快，一个指针慢，那么如果有环，肯两者会遇到


    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
